package code;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
	
	public void dfs(int n,int step,int sum,int[] candidates,int[] pre,List<List<Integer>> result){
		if(sum==0){
			List<Integer> list=new ArrayList<Integer>();
			for(int i=0;i<step;i++){
				list.add(candidates[pre[i]]);
//				System.out.print(candidates[pre[i]]+" ");
			}
//			System.out.println();
			result.add(list);
			return ;
		}
		for(int i=0;i<n;i++){
			if(sum-candidates[i]>=0 && (step==0 || i>=pre[step-1])){
//				System.out.println(step+" "+i);
				pre[step]=i;
				dfs(n,step+1,sum-candidates[i],candidates,pre,result);
			}
		}
	}
	public int mergeSort(int l,int r,int[] array){
		if(l==r){
			return 0;
		}
		int mid=l+r>>1;
		int lcnt=mergeSort(l,mid,array);
		int rcnt=mergeSort(mid+1,r,array);
		int sum=lcnt+rcnt;
		int[] tmp=new int[r-l+1];
		int idx=0;
		int i,j;
		for(i=l,j=mid+1;i<=mid && j<=r;){
			if(array[i]>array[j]){
				sum++;
				tmp[idx++]=array[j];
				j++;
			}
			else{
				tmp[idx++]=array[i];
				i++;
			}
		}
		for(;i<=mid;i++)	tmp[idx++]=array[i];
		for(;j<=r;j++)	tmp[idx++]=array[j];
		for(i=0;i<r-l+1;i++)
			array[l+i]=tmp[i];
		return sum;
	}
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	List<List<Integer>> result=new ArrayList<List<Integer>>();
    	
    	int n=candidates.length;
    	if(n==0)	return result;
    	
    	mergeSort(0, n-1, candidates);
    	int maxSize=target/candidates[0]>100?100:target/candidates[0];
    	int[] pre=new int[maxSize];
    	dfs(n,0,target,candidates,pre,result);
    	
        return result;
    }
    
    public static void main(String[] args){
    	int[] can={1};
    	new CombinationSum().combinationSum(can, 2);
    }
}
